package cn.itcast.algorithm.sort.quicksort;

/**
 * 基础快排算法
 * create by zhangtian105 on 2021/6/15
 */
public class BaseQuickSort {

    public static void baseQuickSort(int waitArray[], int leftIdx, int rightIdx) {
        if (leftIdx < rightIdx) { // 指针未相遇，继续执行分治 将中间的这个数和第一个数交换
            int i = leftIdx, j = rightIdx, targetV = waitArray[leftIdx] ;

            while (i < j) {
                while (i < j && waitArray[j] >= targetV) {// 从右向左找第一个小于x的数
                    j-- ;
                }

                if (i < j) {
                    waitArray[i++] = waitArray[j] ;
                }

                while (i < j && waitArray[i] < targetV) {// 从左向右找第一个大于等于x的数
                    i++ ;
                }

                if (i < j) {
                    waitArray[j--] = waitArray[i] ;
                }
            }

            waitArray[i] = targetV ;

            baseQuickSort(waitArray, leftIdx, i - 1);
            baseQuickSort(waitArray, i + 1, rightIdx);
        }
    }
}
